local error = error

local open = io.open

local find = string.find
local gsub = string.gsub
local len = string.len
local match = string.match
local sub = string.sub

local insert = table.insert
local concat = table.concat
local remove = table.remove

module("xml")

local function parseargs(s)
	local arg = {}
	gsub(s, "(%w+)=([\"'])(.-)%2", function (w, _, a)
			arg[w] = a
		end)
	return arg
end

local function remove_xml_comments(s)
	local r = {}
	while len(s) > 0 do
		local c_start = find(s, "<!--", nil, true)
		if not c_start then
			insert(r, s)
			s = ""
		else
			local c_end = find(s, "-->", c_start + 5, true)
			if not c_end then
				error("Invalid XML : unclosed comment")
			end
			insert(r, sub(s, 1, c_start - 1))
			s = sub(s, c_end + 3, -1)
		end
	end
	return concat(r)
end

local function parsestring(s)
	local stack = {}
	local top = {}
	insert(stack, top)
	local ni,c,label,xarg, empty
	local i, j = 1, 1
	s = remove_xml_comments(s)
	while true do
		ni,j,c,label,xarg, empty = find(s, "<(%/?)(%w+)(.-)(%/?)>", j)
		if not ni then break end
		local text = sub(s, i, ni-1)
		if not match(text, "^%s*$") then
			insert(top, text)
		end
		if empty == "/" then  -- empty element tag
			insert(top, {label=label, xarg=parseargs(xarg), empty=1})
		elseif c == "" then   -- start tag
			top = {label=label, xarg=parseargs(xarg)}
			insert(stack, top)   -- new level
		else  -- end tag
			local toclose = remove(stack)  -- remove top
			top = stack[#stack]
			if #stack < 1 then
				error("nothing to close with "..label)
			end
			if toclose.label ~= label then
				error("trying to close "..toclose.label.." with "..label)
			end
			insert(top, toclose)
		end
		i = j+1
	end
	local text = sub(s, i)
	if not match(text, "^%s*$") then
		insert(stack[#stack], text)
	end
	if #stack > 1 then
		error("unclosed "..stack[#stack].label)
	end
	return stack[1]
end

function parsefile(f)
	local f, err = open(f, "r")
	if not f then return nil, err end
	local s = f:read("*a")
	f:close()
	-- remove the UTF-8 BoM if it exists.
	if s:sub(1, 3) == "\239\187\191" then
		s = s:sub(4)
	end
	return parsestring(s)
end

